package com.heima.leetcode.datastructure.linkedlist;

public class ReverseSinglyLinkedList {

    /**
     * <h3>方法一</h3>
     * 反转链表，用头插法进行反转
     * @param oldHead 以前链表的头节点
     * @return 反转过后的链表的头节点
     */
    public static ListNode reverseList1(ListNode oldHead){
        ListNode newHead = null;
        ListNode p = oldHead;
        while (p != null) {
            newHead = new ListNode(p.val, newHead);
            p = p.next;
        }
        return newHead;
    }

    /**
     * <h3>方法二，面向对象</h3>
     * 反转链表，提供一个集合容器，不创建新的节点，而是改变原节点的指向，省空间
     * @param oldHead 以前链表的的头节点
     * @return 新链表的头节点
     */
    public static ListNode reverseList2(ListNode oldHead){
        List oldList = new List(oldHead);
        List newList = new List(null);
        while (!oldList.isEmpty()) {
            ListNode removed = oldList.removeFirst();
            newList.addFirst(removed);
        }
        return newList.head;
    }

    /**
     * <h3>方法三</h3>
     * 反转链表，用递归实现，递的时候找到最后一个节点，归的时候改变指针指向
     * @param oldHead 以前链表的头节点
     * @return 新链表的头节点
     */
    public static ListNode reverseList3(ListNode oldHead){
        // 递的时候找到最后一个节点
        if (oldHead == null || oldHead.next == null){
            return oldHead;
        }
        ListNode last = reverseList3(oldHead.next);
        // 归的时候改变指针指向
        oldHead.next.next = oldHead;
        oldHead.next = null;
        return last;
    }

    /**
     * <h3>方法四</h3>
     * 把旧链表的头作为新链表的头，每次都把旧链表中的第二个节点脱离下来，接到新链表中去，让第三个节点成为第二个节点
     * @param oldHead 以前链表的头
     * @return 新链表的头
     */
    public static ListNode reverseList4(ListNode oldHead){
        // 链表为空
        if (oldHead == null){
            return null;
        }
        ListNode newHead = oldHead;
        ListNode oldTwo = oldHead.next;
        while (oldTwo != null){
            oldHead.next = oldTwo.next;
            oldTwo.next = newHead;
            newHead = oldTwo;
            oldTwo = oldHead.next;
        }
        return newHead;
    }

    /**
     * <h3>方法五，对比于方法二，此为面向过程</h3>
     * 初始化新链表null，每次取出旧链表的头部，对新链表进行头插法
     * @param oldHead 以前的链表头节点
     * @return 新的链表头节点
     */
    public static ListNode reverseList5(ListNode oldHead){
        ListNode newHead = null;
        while (oldHead != null){
            ListNode oldTwo = oldHead.next;
            oldHead.next = newHead;
            newHead = oldHead;
            oldHead = oldTwo;
        }
        return newHead;
    }

    private static class List{
        ListNode head;

        public List(ListNode head) {
            this.head = head;
        }

        public boolean isEmpty(){
            return head == null;
        }

        public ListNode removeFirst(){
            if (head == null){
                throw new IllegalArgumentException("链表为空");
            }
            ListNode node = head;
            head = node.next;
            return node;
        }

        public void addFirst(ListNode first){
            if (first == null){
                throw new IllegalArgumentException("参数违法");
            }
            first.next = head;
            head = first;
        }
    }
}
